package linkedList;

import stack_queue.Queue;

/**
 * @program: play-structure
 * @description: 链表队列，链表不是对称,插入元素在队尾插入，删除元素在队头删除
 * @author: baichen
 **/
public class LinkedListQueue<E> implements Queue<E> {
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;    //定义 head 头结点与 tail 尾节点
    private int size;

    public LinkedListQueue() {        //参数为空的情形
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    //入队操作
    @Override
    public void enqueue(E e) {
        if (tail == null) {    //判断队尾是否为空
            // 如果为空就直接new一个节点，此时只有一个元素，所以head等于tail
            tail = new Node(e);
            head = tail;
        } else {
            //new 的节点应该在 tail 的 next 的位置
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    //出队操作
    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty");
        }
        Node retNode = head;//出队元素所在的节点应该是 Head 这个位置
        head = head.next;        //新的 head 将会跳过 Node ,直接指向 head.next
        retNode.next = null;    //将 retNode 从链表中断开
        if (head == null) {   //链表只有一个元素时
            tail = null;
        }
        size--;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty");
        }
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");    //链表头的位置是队首，负责出队

        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");    //链表尾的位置是队尾，负责入队
        return res.toString();
    }

    public static void main(String[] args) {

        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for (int i = 0; i < 10; i++) {        //入队10个元素
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {            //每隔3个元素出队1个元素
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}
